package cn.datastructure;

import java.util.ArrayList;

/**
 * 链表反转
 *
 * @author summit
 * @since 2022/5/18 16:57
 */
public class LinkInversionTest {

	public static void main(String[] args) {
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		Node n4 = new Node(4);
		Node n5 = new Node(5);
		n1.setNext(n2);
		n2.setNext(n3);
		n3.setNext(n4);
		n4.setNext(n5);
		Node singleNode = reverseLinkedList(n1);
	}

	/**
	 *  1-> 2 ->3
	 *  第一次： next ->2 head.next -> null ; pre->1  head->2
	 *  第二次： next->3; head.next->1; pre->2 head->3
	 *  1<- 2 ->3
	 *
	 *
	 * @param head
	 * @return
	 */
	public static Node reverseLinkedList(Node head) {

		Node pre = null;
		Node next = null;
		while (head != null) {
			next = head.getNext();
			head.setNext(pre);
			pre = head;
			head = next;
		}
		return pre;
	}

	public static Node reverseDoubleLinkedList(Node head) {

		Node pre = null;
		Node next = null;
		while (head != null) {
			next = head.getNext();
			head.setNext(pre);
			head.setNext(next);
			pre = head;
			head = next;
		}
		return pre;
	}
}



class Node {

	private Integer value;

	private Node next;

	private Node last;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}
}

//			next = head.getNext();
//			head.setNext(pre);
//			pre = head;
//			head = next;